package interview.problem1;

import java.util.*;

/* An adjacency list is one way of representing a graph (another is adjacency 
 * matrix).  Here, the Adjacency list is implemented as an array of LinkedLists.
 * nodeList[v] contains the LinkedList of edges outgoing from v. The edges are 
 * stored as Edge objects, containing the neighbor of v and its distance.
 */
public class AdjacencyList implements GraphRepresentation {
	public AdjacencyList() {
		this.nodeList = new LinkedList[maxNodes];
	}

	// we assume that since only capital letters can be used as nodes,
	final int maxNodes = 27; // 应为限制，最大节点数不能操果27个.
	LinkedList[] nodeList;

	/**  
	* @ClassName: Edge  
	* @Description: 边 
	* @author Alex yaohao@1218.com.cn  
	* @date 2017年2月25日 下午4:40:57  
	*    
	*/
	public class Edge {
		int node;
		int distance;

		public Edge(int node, int distance) {
			this.node = node;
			this.distance = distance;
		}
	}

	private void checkValid(int v) throws GraphException {
		if (v < 0 || v >= maxNodes)
			throw new GraphException("Invalid node");
	}

	/* (非 Javadoc)  
	* <p>Title: addEdge</p>  
	* <p>Description: </p>  
	* @param v1
	* @param v2
	* @param dist
	* @throws GraphException  
	* @see interview.problem1.GraphRepresentation#addEdge(int, int, int)  
	*/
	public void addEdge(int v1, int v2, int dist) throws GraphException {
		checkValid(v1);
		checkValid(v2);
		if (dist < 0)
			throw new GraphException("路径必须 >= 0");

		if (nodeList[v1] == null)
			nodeList[v1] = new LinkedList();

		Edge edge = new Edge(v2, dist);
		nodeList[v1].add(edge);
	} 

	public int distance(int v1, int v2) throws GraphException {
		checkValid(v1);
		checkValid(v2);
		ListIterator i = nodeList[v1].listIterator(0);
		while (i.hasNext()) {
			Edge current = (Edge) i.next(); 
			if (current.node == v2)
				return current.distance;
		}
		throw new GraphException("No such edge");
	}

	public LinkedList getNeighbors(int v) throws GraphException {
		checkValid(v);
		if (nodeList[v] == null)
			nodeList[v] = new LinkedList();
		return nodeList[v];
	}
}
